package cn.zhl.tree.binarysearch;

import cn.zhl.tree.BinaryTree;

import java.util.Comparator;

/**
 * @program: demos
 * @description:
 * @author: 刘振华
 * @create: 2020-04-14 10:38
 **/
public class BinarySearchTree<E> extends BinaryTree<E> {
	private Comparator<E> comparator;

	public BinarySearchTree() {
		this(null);
	}

	public BinarySearchTree(Comparator comparator) {
		this.comparator = comparator;
	}

	/**
	 * 从根节点开始挨个找，如果大的找右节点，如果小的找左节点，直到为null，如果相等，那么就return
	 *
	 * @param e
	 */
	public void add(E e) {
		elementNotNullCheck(e);
		if (root == null) {
			root = createNode(e, null);
			size++;
			afterAdd(root);
			return;
		}
		Node node = root;
		Node parent = root;
		boolean flag = true;//表示右，false表示左
		while (node != null) {
			parent = node;
			int tmp = compareTo(e, node.element);
			if (tmp < 0) {
				node = node.left;
				flag = false;
			} else if (tmp > 0) {
				node = node.right;
				flag = true;
			} else {
				//值相等了就覆盖掉之前的值
				node.element = e;
				return;
			}
		}
		Node rs = createNode(e, parent);
		if (flag) {
			parent.right = rs;
		} else {
			parent.left = rs;
		}
		size++;
		afterAdd(rs);
	}

	protected void afterAdd(Node node) {}

	private Node findByEle(E e) {
		Node node = root;
		while (node != null) {
			int i = compareTo(e, node.element);
			if (i == 0) {
				return node;
			} else if (i > 0) {
				node = node.right;
			} else {
				node = node.left;
			}
		}
		return null;
	}

	private void remove(Node rnode) {
		//首先找到节点
		if (rnode == null) {
			return;
		}
		size--;
		if (rnode.left != null && rnode.right != null) {
			Node pnode = predecessor(rnode);
			rnode.element = pnode.element;
			rnode = pnode;
		}
		Node replace = rnode.left == null ? rnode.right : rnode.left;
		if (replace == null) { //叶子节点
			if (rnode == root) {
				root = null;
			} else {
				if (rnode == rnode.parent.left) {
					rnode.parent.left = replace;
				} else {
					rnode.parent.right = replace;
				}
			}
		} else {
			replace.parent = rnode.parent;
			if (rnode == root) {
				root = replace;
			} else {
				if (rnode == rnode.parent.left) {
					rnode.parent.left = replace;
				} else {
					rnode.parent.right = replace;
				}
			}
			afterRemove(rnode,null);
		}
	}

	protected void afterRemove(Node rnode,Node replacement){}

	public void remove(E e) {
		remove(findByEle(e));
	}

	public boolean contains(E e) {
		return findByEle(e) != null;
	}

	private int compareTo(E e1, E e2) {
		if (comparator != null) {
			return comparator.compare(e1, e2);
		}
		return ((Comparable) e1).compareTo(e2);
	}
}
